import re
class automat:
    def __init__(self):
        self.stanja = []
        self.znakovi = []
        self.prih_stanja = []
        self.pocetno_stanje = ''
        self.prijelazi = {}
    def epsilon_okruzenje(self,stanja):   
        novaStanja = []
        
        while stanja != novaStanja:
            stanja.sort()
            novaStanja = stanja
            for i in stanja:
                if i in self.prijelazi:
                    if '$' in self.prijelazi[i]:
                        for k in self.prijelazi[i]['$']:
                            stanja.append(k)
            stanja.sort()            
        return novaStanja
def main():
    NKA = automat()
    eNKA = automat()
    DKA = automat()
    eNKA.prijelazi = {'q0':{'a':['q1'],'b':['q2'],'c':['q1'],'$':['q1','q3']},'q1':{'a':['q2','q1'],'b':['q1'],'c':['q3'],'$':['q2']},'q2':{'a':['q2'],'b':['q1'],'c':['q3']},'q3':{'a':['q2']}}
    eNKA.stanja = ['q2','q1','q3','q0']
    eNKA.pocetno_stanje='q0'
    eNKA.prih_stanja.append('q2')
    eNKA.znakovi = ['a','b','c','$']
    NKA.stanja = eNKA.stanja
    NKA.znakovi = eNKA.znakovi.remove('$')
    NKA.znakovi = eNKA.znakovi
    print(NKA.znakovi)
    NKA.prih_stanja = eNKA.prih_stanja
    NKA.pocetno_stanje = eNKA.pocetno_stanje
    for i in eNKA.stanja:
        eps = eNKA.epsilon_okruzenje([i])
        for j in eNKA.znakovi:
            tmp = []
            got = []
            for t in eps:
                try:
                    for a in eNKA.prijelazi[t][j]:
                        if a not in tmp:
                            tmp.append(a)
                except:
                    continue
            for t in tmp:
                list = eNKA.epsilon_okruzenje([t])
                for a in list:
                    if a not in got:
                        got.append(a)
            if len(got)>0:
                if i in NKA.prijelazi.keys():
                    NKA.prijelazi[i].update({j:got})
                else:
                    NKA.prijelazi.update({i:{j:got}})
            
    st = [eNKA.pocetno_stanje]
    list = eNKA.epsilon_okruzenje(st)
    list.remove(eNKA.pocetno_stanje)
    for i in list:
        if i in NKA.prih_stanja:
            NKA.prih_stanja.append(eNKA.pocetno_stanje)
            break
    print(NKA.pocetno_stanje)
    print(NKA.prih_stanja)
    print(NKA.prijelazi)
    print(NKA.stanja)
    print(NKA.znakovi)
    
    DKA.pocetno_stanje = NKA.pocetno_stanje
    DKA.stanja = [NKA.pocetno_stanje]
    DKA.znakovi = NKA.znakovi
    novi=[]
    for z in NKA.prijelazi[NKA.pocetno_stanje]:
        tmp=''
        tmp2=[]
        for a in NKA.prijelazi[NKA.pocetno_stanje][z]:
            tmp2.append(a)
        tmp2.sort()
        for each in tmp2:
            tmp+=each+','
        tmp = tmp[:len(tmp)-1]
        #if tmp not in DKA.stanja:
            #novi.append(tmp)
        if tmp not in DKA.stanja + novi:
            novi.append(tmp)
        if NKA.pocetno_stanje in DKA.prijelazi.keys():
            DKA.prijelazi[NKA.pocetno_stanje].update({z:tmp})
        else:
            DKA.prijelazi.update({NKA.pocetno_stanje:{z:tmp}})
    while len(novi) >0:
        novi_novi=[]
        DKA.stanja+=novi
        for stanje in novi:
            for znak in DKA.znakovi:
                tmp=''
                tmp2=[]
                for jed in re.split(',',stanje):
                    try:
                        for a in NKA.prijelazi[jed][znak]:
                            if a not in tmp2:
                                tmp2.append(a)
                    except:
                        continue    
                tmp2.sort()
                for each in tmp2:
                    tmp+=each+','
                if tmp != '':
                    tmp = tmp[:len(tmp)-1]
                    if tmp not in DKA.stanja + novi_novi:
                        novi_novi.append(tmp)
                    if stanje in DKA.prijelazi.keys():
                        DKA.prijelazi[stanje].update({znak:tmp})
                    else:
                        DKA.prijelazi.update({stanje:{znak:tmp}})
        novi=novi_novi
    for stanje in DKA.stanja:
        for a in re.split(',',stanje):
            if a in NKA.prih_stanja and stanje not in DKA.prih_stanja:
                DKA.prih_stanja.append(stanje)
    print(DKA.prih_stanja)
    print(DKA.prijelazi)
    print(DKA.stanja)
    
    
    
    
    
    
    
if __name__ == '__main__':
    main()